package com.shine.demo.leetCode.leetCode1029;

import com.shine.demo.leetCode.entity.ListNode;

/**回文链表
 *
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */
public class IsPalindrome {


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(2);
        ListNode l4 = new ListNode(1);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        System.out.println(isPalindrome1(l1));
    }

    public static ListNode copy(ListNode head) {
        if (null == head) {
            return head;
        }
        ListNode copy = new ListNode(head.val);
        ListNode copyNext = copy;
        while (head.next != null) {
            copyNext.next = new ListNode(head.next.val);
            head = head.next;
            copyNext = copyNext.next;
        }
        return copy;
    }


    public static boolean isPalindrome1(ListNode head) {
        ListNode copy = new ListNode(head.val);
        ListNode copyNext = copy;
        //上一个节点
        ListNode pre = null;
        //下一个节点
        ListNode next = null;
        while (head != null) {
            next = head.next;
            if(null != next){
                copyNext.next = new ListNode(head.next.val);
            }
            head.next = pre;
            pre = head;
            head = next;
            copyNext =copyNext.next;
        }
        while (null != pre.next) {
            if (pre.val != copy.val) {
                return false;
            }
            if(pre.val == pre.next.val){
                break;
            }
            pre = pre.next;
            copy = copy.next;
        }
        return true;

    }
    public static boolean isPalindrome2(ListNode head) {
        ListNode copy = new ListNode(head.val);
        ListNode copyNext = copy;
        while (head != null) {
            if (null != head.next ) {
                if(head.val==head.next.val){
                    head = head.next;
                    break;
                }
                copyNext.next = new ListNode(head.next.val);
                copyNext = copyNext.next;
            }
            head = head.next;
        }
        while (null != head.next) {
            if (head.val != copy.val) {
                return false;
            }
            head = head.next;
            copy = copy.next;
        }
        return true;

    }




}
